#!/usr/bin/python
# -*- coding: utf-8 -*-
import numpy as np
import matplotlib.pyplot as plot
from math import sqrt

# 线性扫描法
# 训练数据集 T = {(x1,y1)....(xn,yn)}
# 待预测数据 x_test
# k值
# 1.计算x_test与xi的欧式距离
# 2.欧式距离排序
# 3.取前k个最小距离，对应训练数据点的类型y
# 4.对k个y值进行统计
# 5.返回频率出现最高的y值

class KNN():
    def __init__(self,k):
        self.k = k 

    def fix(self,x_test,dataset,labels):
        sample_number = dataset.shape[0] # 取行数

        # step1: 计算分类数据与各个训练数据集之间的欧式距离
        diff = np.tile(x_test,(sample_number,1)) - dataset
        square_dist = diff**2
        distance = (square_dist.sum(axis=1))**0.5 # 按行累加开根号

        # step2: 按距离排序,返回数组排序后的值对应的索引值
        sort_distance = distance.argsort()

        class_count = {} #用来记录对应类的个数
        # step3: 表决法
        for i in range(self.k):
            vote_label = labels[sort_distance[i]] #获取第i个值的label
            class_count[vote_label] = class_count.get(vote_label,0) + 1
        
        # 返回k个值中类别个数最多的那个类别
        sorted_class_count = sorted(class_count.items(),key=lambda item:item[1],reverse=True)

        return sorted_class_count[0][0]

if __name__ == "__main__":
    dataset = np.array([[5,4],
                        [9,6],
                        [4,7],
                        [2,3],
                        [8,1],
                        [7,2]])
    labels = np.array([1,1,1,-1,-1,-1])

    # 测试数据
    x_test = np.array([[5,3]])

    knn = KNN(3)
    res = knn.fix(x_test, dataset, labels)

    print("x_test被分类为{}" , res)    

